//给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。 
//
// 示例: 
//
// 输入: n = 4, k = 2
//输出:
//[
//  [2,4],
//  [3,4],
//  [2,3],
//  [1,2],
//  [1,3],
//  [1,4],
//] 
// Related Topics 回溯算法 
// 👍 338 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

//Java：组合
public class P77Combinations {

    /**
     *
     * 思路： 回溯算法，可以参考46题全排列来做
     *
     * 执行用时： 38 ms , 在所有 Java 提交中击败了 15.99% 的用户 内存消耗： 41 MB , 在所有 Java 提交中击败了 78.82% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private List<List<Integer>> list = new ArrayList<>();

        public List<List<Integer>> combine(int n, int k) {
            dfs(1, n, k, new Stack<>(), new boolean[n + 1]);
            return list;
        }

        private void dfs(int start, int n, int k, Stack<Integer> stack, boolean[] used) {
            // 符合要求的
            if (stack.size() == k) {
                list.add(new ArrayList<>(stack));
            }

            for (int i = start; i <= n; i++) {
                // 去重
                if (used[i]) {
                    continue;
                }
                used[i] = true;
                stack.push(i);

                dfs(i, n, k, stack, used);

                stack.pop();
                used[i] = false;

            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P77Combinations().new Solution();
        System.out.println(solution.combine(0, 0));
        // TO TEST
    }

}